Distributed Algorithms in an Ergodic Markovian Environment
Identifieur interne : 005D55 ( Main/Exploration ); précédent : 005D54; suivant : 005D56Distributed Algorithms in an Ergodic Markovian Environment
Auteurs : Francis Comets ; François Delarue ; René SchottSource :
English descriptors
Abstract
We provide a probabilistic analysis of the banker algorithm when transition probabilities may depend on time and space. The transition probabilities evolve, as time goes by, along the trajectory of an ergodic Markovian environment, whereas the spatial parameter just acts on long runs. Our model appears as a new (small) step towards more general time and space dependent protocols. Our analysis relies on well-known results in stochastic homogenization theory and investigates the asymptotic behaviour of the rescaled algorithm as the total amount of resource available for allocation tends to the infinity. In the two dimensional setting, we manage to exhibit three different possible regimes for the deadlock time of the limit system.
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Crin, to step Corpus: 004076
- to stream Crin, to step Curation: 004076
- to stream Crin, to step Checkpoint: 000203
- to stream Main, to step Merge: 005F78
- to stream Main, to step Curation: 005D55
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" wicri:score="491">Distributed Algorithms in an Ergodic Markovian Environment</title></titleStmt><publicationStmt><idno type="RBID">CRIN:comets05a</idno><date when="2005" year="2005">2005</date><idno type="wicri:Area/Crin/Corpus">004076</idno><idno type="wicri:Area/Crin/Curation">004076</idno><idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Curation">004076</idno><idno type="wicri:Area/Crin/Checkpoint">000203</idno><idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Checkpoint">000203</idno><idno type="wicri:Area/Main/Merge">005F78</idno><idno type="wicri:Area/Main/Curation">005D55</idno><idno type="wicri:Area/Main/Exploration">005D55</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Distributed Algorithms in an Ergodic Markovian Environment</title><author><name sortKey="Comets, Francis" sort="Comets, Francis" uniqKey="Comets F" first="Francis" last="Comets">Francis Comets</name></author><author><name sortKey="Delarue, Francois" sort="Delarue, Francois" uniqKey="Delarue F" first="François" last="Delarue">François Delarue</name></author><author><name sortKey="Schott, Rene" sort="Schott, Rene" uniqKey="Schott R" first="René" last="Schott">René Schott</name></author></analytic></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>distributed algorithms</term><term>random environment</term><term>reflected diffusion</term><term>stochastic homogenization</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en" wicri:score="2617">We provide a probabilistic analysis of the banker algorithm when transition probabilities may depend on time and space. The transition probabilities evolve, as time goes by, along the trajectory of an ergodic Markovian environment, whereas the spatial parameter just acts on long runs. Our model appears as a new (small) step towards more general time and space dependent protocols. Our analysis relies on well-known results in stochastic homogenization theory and investigates the asymptotic behaviour of the rescaled algorithm as the total amount of resource available for allocation tends to the infinity. In the two dimensional setting, we manage to exhibit three different possible regimes for the deadlock time of the limit system.</div></front></TEI><affiliations><list></list><tree><noCountry><name sortKey="Comets, Francis" sort="Comets, Francis" uniqKey="Comets F" first="Francis" last="Comets">Francis Comets</name><name sortKey="Delarue, Francois" sort="Delarue, Francois" uniqKey="Delarue F" first="François" last="Delarue">François Delarue</name><name sortKey="Schott, Rene" sort="Schott, Rene" uniqKey="Schott R" first="René" last="Schott">René Schott</name></noCountry></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 005D55 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 005D55 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= CRIN:comets05a
|texte= Distributed Algorithms in an Ergodic Markovian Environment
}}
| This area was generated with Dilib version V0.6.33. |  |